/**
 * 1047. 删除字符串中的所有相邻重复项
 * https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/
 */
public class Solutions_1047 {
    public static void main(String[] args) {
        String str = "abbaca";  // output: "ca"

        String result = removeDuplicates(str);
        System.out.println(result);
    }

    /**
     * 解题思路：栈
     * 利用数组方式来实现栈
     */
    public static String removeDuplicates(String S) {
        if (S == null) {
            return null;
        }
        int idx = 0;
        char[] arr = S.toCharArray();
        char[] stack = new char[arr.length];

        for (int i = 0; i < arr.length; i++) {
            if (idx > 0 && stack[idx - 1] == arr[i]) {
                // 弹出
                idx -= 1;
                continue;
            }
            stack[idx ++] = arr[i];
        }
        // 最终 stack 数组中的有效元素个数是 idx 个
        return String.valueOf(stack, 0, idx);
    }
}
